import java.util.*;

class Node {
    int data = 0;
    Node next = null;

    public Node() {}

    public Node(int data) {
        this.data = data;
    }

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}

public class MyListTest2 {
    static final Scanner sc = new Scanner(System.in);
    //有头 / 无头
    //单向 / 双向
    //循环 / 不循环
    //有序 / 无序

    //有头单向不循环链表
    static public void main(String [] args) {
        Node head = new Node(), newObj = null;
        Node tail = head;
        int num;

        while (true) {
            System.out.printf("请输入数据: ");
            num = sc.nextInt();

            if (num == -1)
                break;

            newObj = new Node(num);

            for (tail = head;
                    tail.next != null && num > tail.next.data;
                    tail = tail.next)
                ;
            newObj.next = tail.next;
            tail.next = newObj;
        }

        tail = head.next;
        while (tail != null) {
            System.out.printf("%d ", tail.data);
            tail = tail.next;
        }
        System.out.println();
    }

    //无头单向不循环链表
    static public void noHeadList() {
        Node head = null, newObj = null, tail = null;
        int num;

        while (true) {
            System.out.printf("请输入数据: ");
            num = sc.nextInt();

            if (num == -1)
                break;

            newObj = new Node(num);

            if (head == null) {
                head = newObj;
            } else {
                tail.next = newObj;
            }

            tail = newObj;
        }

        /*
         * head.data
         * head.next.data
         * head.next.next.data
         * head.next.next.next.data
         */

        tail = head;
        while (tail != null) {
            System.out.printf("%d ", tail.data);
            tail = tail.next;
        }
        System.out.println();
    }
}
